package Bridges;

import DFS.Graph;

import java.util.ArrayList;
import java.util.List;

public class FindBridges {
    private Graph graph;
    private boolean[] visited;

    private int[] ord;
    private int[] low;
    private int cnt;

    private List<Edge> res;

    public FindBridges(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.getVertexNum()];

        res = new ArrayList<>();
        ord = new int[graph.getVertexNum()];
        low = new int[graph.getVertexNum()];
        cnt = 0;
        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!visited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        ord[v] = cnt;
        low[v] = ord[v];
        cnt++;
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
                low[v] = Math.min(low[v], low[w]);
                if (low[w] > ord[v]) {
                    res.add(new Edge(v, w));
                }
            } else if (w != parent) {
                low[v] = Math.min(low[v], low[w]);
            }
        }
    }

    public List<Edge> result() {
        return res;
    }

    public static void main(String[] arg) {
        Graph g = new Graph("Olag.txt");
        FindBridges fb = new FindBridges(g);
        System.out.println(fb.result());

        Graph g2 = new Graph("gDfs.txt");
        FindBridges fb2 = new FindBridges(g2);
        System.out.println(fb2.result());

        Graph tree = new Graph("gNoCycle.txt");
        //System.out.println(tree);
    }
}
